package com.interview.javabase.algorithm;

/**
 * @author: zsg
 * @description:希尔排序
 * @date: 2019/8/25 20:01
 * @modified:
 */
public class DonaldShellSort {

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{8, 9, 1, 7, 2, 3, 5, 4, 6};
//        swap(arr);
        move(arr);
        for (int j = 0; j < arr.length; j++) {
            Integer integer = arr[j];
            System.out.print(integer + " ");
        }

    }

    /**
     * 交换法
     *
     * @param arr
     */
    private static void swap(Integer[] arr) {
        // 循环分组
        for (int step = arr.length / 2; step > 0; step /= 2) {
            for (int i = step; i < arr.length; i++) {
                // 遍历每组的所有元素就是循环交换
                for (int j = i - step; j >= 0; j -= step) {
                    if (arr[j] > arr[j + step]) {
                        int temp = arr[j];
                        arr[j] = arr[j + step];
                        arr[j + step] = temp;
                    }
                }
            }
        }
    }

    /**
     * 移位法
     *
     * @param arr
     */
    private static void move(Integer[] arr) {
        // 循环分组
        for (int step = arr.length / 2; step > 0; step /= 2) {
            for (int i = step; i < arr.length; i++) {

                // 待插入值的下标
                int j = i;
                // 待插入的值
                int temp = arr[j];
                if (arr[j] < arr[j - step]) {
                    while (j - step >= 0 && temp < arr[j - step]) {
                        arr[j] = arr[j - step];
                        j -= step;
                    }
                    arr[j] = temp;
                }
            }

        }
    }
}
